1. Field of the Invention
The present invention relates to routing in multi-hop (e.g., wireless) mesh networks, and, more particularly, to the routing of flows and scheduling of transmissions to achieve a given rate vector.
2. Description of the Related Art
Wireless multi-hop networks have attracted a lot of attention in recent years as the next evolutionary step for wireless data networks. In multi-hop networks, communication between two end nodes is carried out through a number of intermediate nodes whose function is to relay information from one point to another. In a typical wireless multi-hop mesh network, small nodes that act as simple routers are installed throughout a site (e.g., a home, business, or office) by simply plugging them into power outlets. Each node then transmits a low-power signal capable of reaching neighboring nodes, which in turn transmit to successive nodes, with the process being repeated until the data arrives at its destination.
Multi-hop networks have evolved into two distinct classes: fixed-mesh networks and mobile ad-hoc networks. In a fixed-mesh network, nodes are fixed in place and are typically endowed with more power resources than nodes in a mobile ad-hoc network. However, in both these network classes, wireless nodes possess limited communication capabilities. One of these limitations is the number of neighbors that these nodes can communicate with simultaneously. This is primarily determined by the channel model: either a single shared channel or a set of orthogonal communication channels. From a medium-access protocol perspective, in a shared-channel model, interference from ongoing neighboring transmissions on the same channel can prevent successful transmissions between two nodes. In the model employing a set of orthogonal communication channels, neighboring transmissions are possible using different (orthogonal) channels.
A problem that arises in wireless multi-hop networks that use orthogonal channels for communication between nodes is characterizing the rates that are achievable. One solution to this problem is to use polynomial-time approximation algorithms to route flows and schedule transmissions in a scenario in which each node is allowed to be in communication with at most one other node at any time instant. However, this solution does not address the scenario in which a node is allowed to engage in multiple simultaneous communications with its neighbors, which introduces various system-design and physical-layer constraints. This multiple simultaneous communication scenario is ever more common due to the availability of multiple orthogonal channels in existing and proposed wireless standards and the use of multiple receivers (radios) within a single wireless device.